/*
  区间排序
  1.1 题面描述
    小杨有一个包含 n 个正整数的序列 a。
    小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 [l, r] (l <= r),
    并对区间内所有数字，即 al, a(l+1), ... , ar 进行升序排序。
    每次升序排序会在上一次升序排序的结果上进行。
    小杨想请你计算出多次升序排序后的序列。
  1.2 输入格式
    第一行包含一个正整数 n， 含义如题面所示。
    第二行包含 n 个正整数 a1, a2, ... , an，代表序列。
    第三行包含一个正整数 q， 代表排序次数。
    之后 q 行，每行包含两个正整数 li 和 ri，代表将区间 [li, ri] 内所有数字进行升序排序。
  1.3 输出格式
    输出一行包含 n 个正整数， 代表多次升序排序后的序列。
  1.4 样例1
    输入
      5
      3 4 5 2 1
      3
      4 5
      3 4
      1 3
    输出
      1 3 4 5 2
    说明：
      第一次升序排序后，序列为 [3, 4, 5, 1, 2]；
      第二次升序排序后，序列为 [3, 4, 1, 5, 2]；
      第三次升序排序后，序列为 [1, 3, 4, 5, 2]；
  1.5 数据范围
    对于全部数据，保证有
       1 <= n <= 100,
       1 <= ai <= 100,
       1 <= q <= 100,
       1 <= li <= ri <= n。
*/